package com.zklh.leetcode.chain;

/**
 * 反转链表实现
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/3/28 17:51
 */
public class ReverseChain {


    /**
     * 反转 m -> n, 索引从1开始 m,n表示距离head n的位置
     * @param head
     * @param m
     * @param n
     */
    public Node reverseBetween(Node head, int m, int n) {

        if (m == 1) {
           return reverseN(head, n);
        }
        head.next = reverseBetween(head.next, m-1,n-1);
        return head;
    }

    /**
     * 反转 head 这个链条, 反转前n个元素,  返回翻转后的头结点
     * @param head
     * @param n
     * @return
     */
    public Node reverseN(Node head, int n) {

        if (n == 1) {
            return head;
        }
        Node last = reverseN(head, n-1);
        Node nowNode = head.next;
        Node tempNode = nowNode.next;
        nowNode.next = last;
        head.next = tempNode;
        return nowNode;
    }


    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node now = this;
            while (now != null) {
                sb.append(now.val).append("->");
                now = now.next;
            }
            return sb.substring(0, sb.length()-2);
        }
    }



    public static void main(String[] args) {
        Node head = new Node(1);
        Node now = head;
        for (int i = 2; i < 7; i++) {
            now.next = new Node(i);
            now = now.next;
        }
        System.out.println("reverse before");
        System.out.println(head);

        System.out.println("reverse after");
        ReverseChain reverseChain = new ReverseChain();
        head = reverseChain.reverseBetween(head,3,5);
        System.out.println(head);

    }

}
